#include "LinkTree.h"
#include <iostream>

Node::Node(ElementType element)
{
    data = element;
    parent = nextSibling = firstChild = nullptr;
}

Node *Node::GetParent() const
{
    return parent;
}

ElementType Node::GetData() const
{
    return data;
}

void Node::Connect(Node *parent)
{
    if(parent == nullptr)
        return;
    
    this->parent = parent;
    //头插
    this->nextSibling = parent->firstChild;
    parent->firstChild = this;
}

void Node::DisConnect()
{
    if(parent == nullptr)
        return;

    if(this == parent->firstChild)
    {
        parent->firstChild = this->nextSibling;
    }
    else
    {
        Node *travelPoint = parent->firstChild;
        while(travelPoint->nextSibling != nullptr)
        {   
            if(travelPoint->nextSibling == this)
            {
                travelPoint->nextSibling = this->nextSibling;
                break;
            }
            travelPoint = travelPoint->nextSibling;
        }    
    }
    nextSibling = nullptr;
    parent = nullptr;
}

void Node::TravelNode(Node *node,int depth,void(*showPtr)(ElementType))
{
    if(node == nullptr)
        return;
    for(int i = 0; i < depth;i++)
        printf("  ");
    if(depth!= 0)
        printf("%s","|_");
    showPtr(node->data);
    TravelNode(node->firstChild,depth+1,showPtr);
    TravelNode(node->nextSibling,depth,showPtr);
   
    
}


LinkTree::LinkTree()
{
   root = new Node(0);
}

LinkTree::~LinkTree()
{
    FreeNode(root);
}

Node *LinkTree::GetRoot() const
{
    return root;
}

int LinkTree::GetTreeHeight()
{   

    return GetNodeHeight(root)-1;
}

Node*LinkTree::FindNode(ElementType element)
{
    return FindNode(root->firstChild,element);
}

void LinkTree::SetShowtype(void (*showPtr)(ElementType element))
{
    this->showPtr = showPtr;
}

void LinkTree::SetFindType(bool (*IsEqual)(ElementType,ElementType))
{
    this->IsEqualPtr = IsEqual;
}

void LinkTree::show()
{
    Node::TravelNode(root->firstChild,0,showPtr);
}

Node*LinkTree::FindNode(Node *node, ElementType element)
{
    if(node == nullptr)
        return nullptr;

    if(IsEqualPtr(node->data,element))
        return node;

    Node *targetNode = FindNode(node->nextSibling,element);
        if(targetNode)
            return targetNode;

    targetNode = FindNode(node->firstChild,element);
        if(targetNode)
            return targetNode;

    return nullptr;
}

void LinkTree::FreeNode(Node *node)
{
    if(node == nullptr)
        return;
    // Node *travelPoint =  node->firstChild;
    // while(travelPoint != nullptr)
    // {
    //     Node *nextNode = travelPoint->nextSibling;
    //     FreeNode(travelPoint);
    //     travelPoint = nextNode;
    // }
    FreeNode(node->firstChild);
    FreeNode(node->nextSibling);
    delete node;
}

int LinkTree::GetNodeHeight(Node *node)
{   
    if(node == nullptr)
        return 0;

    int MaxChildheight = 0;
    Node *travelPoint = node->firstChild;
    while(travelPoint != nullptr)
    {
        int childHeight = GetNodeHeight(travelPoint);
        MaxChildheight = MaxChildheight > childHeight ? MaxChildheight : childHeight;
        travelPoint = travelPoint->nextSibling;
    }
    return MaxChildheight + 1;
}
